package leecode

import "sort"

func permuteUniqueLCR(nums []int) (result [][]int) {
	sort.Ints(nums)
	used1 := make([]bool, len(nums)) //每一层去重
	used2 := make([]bool, len(nums)) //一条枝干去重
	path := make([]int, 0, len(nums))
	var backtracking func(used1, used2 []bool)
	backtracking = func(used1, used2 []bool) {
		if len(path) == len(nums) {
			temp := make([]int, len(path))
			copy(temp, path)
			result = append(result, temp)
		}
		for i := 0; i < len(nums); i++ {
			if used1[i] {
				continue
			}
			if i > 0 && !used2[i-1] && nums[i] == nums[i-1] {
				continue
			}
			used1[i] = true
			used2[i] = true
			path = append(path, nums[i])
			backtracking(used1, used2)
			used1[i] = false
			used2[i] = false
			path = path[:len(path)-1]
		}
	}
	backtracking(used1, used2)
	return result
}
